package leetcode_周赛._2023._03;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 337 场周赛
 * AC_3
 *
 * @author yezh
 * @date 2023/3/19 19:58
 * @see <a>https://www.bilibili.com/video/BV1EL411C7YU/?spm_id_from=444.41.list.card_archive.click&vd_source=80c993386cc8e1d07d0fd43142695518</a>
 */
public class _19 {

    /**
     * 奇偶位数
     * 算法: 位运算
     */
    public int[] evenOddBit(int n) {
        int[] ans = new int[2];
        for (int i = 0; n > 0; n >>= 1) {
            if ((n & 1) == 1) ans[i]++;
            i ^= 1;
        }
        return ans;
    }

    /**
     * 检查骑士巡视方案
     * 算法: 哈希表
     */
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) return false;
        // 垂直两个, 水平一个; 垂直一个, 水平两个
        int n = grid.length;
        Map<Integer, int[]> map = new HashMap<>(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) map.put(grid[i][j], new int[]{i, j});
        for (int i = 1; i < n * n; i++) {
            int[] pre = map.get(i - 1), cur = map.get(i);
            int a = pre[0] - cur[0], b = pre[1] - cur[1];
            if (a * a + b * b != 5) return false;
        }
        return true;
    }

    /**
     * 美丽子集的数目
     * 算法: 回溯
     */
    int ans;
    Set<Integer> path;

    public int beautifulSubsets(int[] nums, int k) {
        // 题目要求非空
        ans = -1;
        path = new HashSet<>();
        dfs(0, nums, k);
        return ans;
    }

//    void dfs(int i, int[] nums, int k) {
//        if (i == nums.length) {
//            ++ans;
//            return;
//        }
//        dfs(i + 1, nums, k);
//
//        if (!(path.contains(nums[i] - k) || path.contains(nums[i] + k))) {
//            path.add(nums[i]);
//            dfs(i + 1, nums, k);
//            path.remove(nums[i]);
//        }
//    }

    void dfs(int i, int[] nums, int k) {
        ++ans;
        if (i == nums.length) return;

        for (; i < nums.length; i++)
            if (!(path.contains(nums[i] - k) || path.contains(nums[i] + k))) {
                path.add(nums[i]);
                dfs(i + 1, nums, k);
                path.remove(nums[i]);
            }
    }

}
